// 1 2 3 4
// 2 4 6 8
// 3 6 9 12
// 4 8 12 16
class Solution {
    public:
        int findKthNumber(int m, int n, int k) {
            auto check = [&](int mid){
                int cnt = 0;
                for(int i = 1;i <= m;i++){
                    cnt += min((mid - 1)/i,n);
                }
                return cnt >= k;
            };
    
            int left = 1,right = m*n;
            while(left <= right){
                int mid = (left + right) >> 1;
                if(check(mid)){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
                
            }
            return right;
        }
    };

// 1 2 3 4
// 2 4 6 8
// 3 6 9 12
// 4 8 12 16
class Solution {
    public:
        int findKthNumber(int m, int n, int k) {
            auto check = [&](int mid){
                int cnt = 0;
                for(int i = 1;i <= m;i++){
                    cnt += min((mid)/i,n);
                }
                return cnt >= k;
            };
    
            int left = 1,right = m*n;
            while(left <= right){
                // cout <<left <<' ' <<right << endl;
                int mid = (left + right) >> 1;
                if(check(mid)){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
                
            }
            return left;
        }
    };

    class Solution {
        public:
            int kthSmallest(vector<vector<int>>& matrix, int k) {
                int n = matrix.size();
                
                auto check = [&](int mid){
                    int j = n - 1,cnt = 0;
                    for(int i = 0;i < n;i++){
                        while(j >= 0 && matrix[i][j] > mid)
                            j--;
                        cnt += j + 1;
                    }
                    return cnt >= k;
                };
        
        
        
        
        
                int left = matrix[0][0],right = matrix[n - 1][n - 1] ;
                while(left <= right){
                    int mid = (left + right) >> 1;
                    if(check(mid)){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }
                return left;
            }
        };

        class Solution {
            public:
                int smallestDistancePair(vector<int>& nums, int k) {
                    int n = nums.size();
                    sort(nums.begin(),nums.end());
                    auto check = [&](int mid){
                        int i = 1,j = 0,ans = 0;
                        for(;i < n;i++){
                            while(nums[i] - nums[j] > mid){
                                j++;
                            }
                            ans += (i - j);
                        }
                        return ans >= k;
                    };
            
            
            
                    int left = 0,right = nums[n - 1];
                    while(left <= right){
                        // cout << left << ' ' << right << endl;
                        int mid =(left + right) >> 1;
                        if(check(mid)){
                            right = mid - 1;
                        }else{
                            left = mid + 1;
                        }
                    }
                    return left;
                }
            };
int N = 1e9 + 7;
int fun2(int a, int b) {
    // cout << a << ' ' << b << endl;
    if (b == 0) {
        return a;
    }
    return fun2(b, a % b);
}
int fun(int a, int b, int t) { return a * b / t; }
class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        if (a > b)
            swap(a, b);
        // if (b % a == 0) {
        //     return (long long)(a % N) * (n % N) % N;
        // }
        long right = (long) min(a, b) * n, left = 0;
        int t = a * b / fun2(a, b);

        // auto check = [&](long long mid) {
        //     return (mid / a + mid / b - mid / t) >= n;
        // };

        while (left <= right) {
            // cout << left << ' ' << right << endl;
            long mid = left + (right - left) / 2;
            if ((mid / a + mid / b - mid / t) >= n) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left % N;
    }
};

using ll = long long;
ll fun(int a, int b) {
    // cout <<a << ' ' << b <<endl;
    return b == 0 ? a : fun(b, a % b);
}
class Solution {
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        long long ab = (ll)a * b / fun(a, b), ac = (ll)a * c / fun(a, c),
                  bc = (ll)b * c / fun(b, c);
        long long abc = (ll)ab * c / fun(ab, c);
        // cout << ab << ' ' << ac <<' ' << bc << ' '<<abc;
        ll left = 0, right = min(min(a, b), c) * n;
        while (left <= right) {
            ll mid = (left + right) >> 1;
            if (mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac +
                    mid / abc 
                    >=n
                ) 
            {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};


using ll = long long;
class Solution {
public:
    int fun(int k){
        ll left = 0,right = (ll)5*k;
        auto check = [&](ll mid){
            ll x = 5,cnt = 0;
            while(x <= mid){
                cnt += mid/x;
                x*=5;
            }
            return cnt;
        };
        while(left <= right){
            ll mid = (left + right) >> 1;
            ll cnt = check(mid);
            // cout << left <<' ' << right << ' ' << cnt << endl;
            if(cnt == k){
                return 5;
            }else if(cnt > k){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return 0;
    }
    int preimageSizeFZF(int k) {
        return fun(k);
    }
};

class Solution {
    public:
        vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int n = nums1.size(),m = nums2.size();
            vector<vector<int>> ans;
            priority_queue<tuple<int,int,int>> pq;
            for(int i = 0;i < min(n,k);i++){
                pq.emplace(-nums1[i] - nums2[0],i,0);
            }
            while(ans.size() < k){
                auto [_,i,j] = pq.top();
                pq.pop();
                ans.push_back({nums1[i],nums2[j]});
                if(j + 1 < m){
                    pq.emplace(-nums1[i] - nums2[j + 1],i,j + 1);
                }
            }
            return ans;
        }
    };